package leet17phonenumcombine

// 思路:
// 号码键：搞一个字符映射。比如 '2' => "abc", '3'=> "def"
// 给定 "23" 按照号码字符遍历，每个号码字符从映射中取出一个字母字符，遍历完一遍，得到一个结果，然后回溯一下，得到一个新结果，重复回溯过程即可。
func LetterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	phoneToLetter := map[byte]string{
		'2': "abc",
		'3': "def",
		'4': "ghi",
		'5': "jkl",
		'6': "mno",
		'7': "pqrs",
		'8': "tuv",
		'9': "wxyz",
	}
	result := []string{}
	// 抽象一个组合字符的组合方法
	// 从第i个号码字符中逐个获取组合元素，每获取到一个，就尝试着继续去第i+1个号码字符中去添加新的组合元素，依次递归组合出所有的元素。
	// 当本地组合结束之后，回退一个位置，留给逐个遍历中的下一个位置。
	var path []byte // 记录当前的组合信息
	var backtrack func(pos int)
	backtrack = func(pos int) {
		if len(path) == len(digits) {
			pathCopy := make([]byte, len(path))
			copy(pathCopy, path)
			result = append(result, string(pathCopy))
			return
		}
		if pos >= len(digits) {
			return
		}
		letter := phoneToLetter[digits[pos]]
		for i := 0; i < len(letter); i++ {
			path = append(path, letter[i])
			backtrack(pos + 1)
			path = path[:len(path)-1]
		}
	}
	backtrack(0)
	return result
}
